Recoverable robust spanning tree problem under interval uncertainty representations

摘要

This paper deals with the recoverable robust spanning tree problem underinterval uncertainty representations. A polynomial time, combinatorialalgorithm for the recoverable spanning tree problem is first constructed. Thisproblem generalizes the incremental spanning tree problem, previously discussedin literature. The algorithm built is then applied to solve the recoverablerobust spanning tree problem, under the traditional interval uncertaintyrepresentation, in polynomial time. Moreover, the algorithm allows to obtain,under some mild assumptions about the uncertainty intervals,severalapproximation results for the recoverable robust spanning tree problem underthe Bertsimas and Sim interval uncertainty representation and the intervaluncertainty representation with a budget constraint.